/*
 * @Author       : wangzeyu 2309335887@qq.com
 * @Date         : 2023-07-16 19:21:48
 * @LastEditors  : WangZeYu
 * @LastEditTime : 2023-07-23 18:43:48
 * @FilePath     : \my-study-js\algorithm\LCS.js
 * @Description  : LCS(最长公共子序列)(动态规划 Dynamic progamming)
 */
// ' a c b a e d '
// ' a b c a d f '
// [  j  a  b  c  a  d  f
// i [0, 0, 0, 0, 0, 0, 0],
// a [0, 1, 1, 1, 1, 1, 1],
// c [0, 1, 1, 2, 2, 2, 2],
// b [0, 1, 2, 2, 2, 2, 2],
// a [0, 1, 2, 2, 3, 3, 3],
// e [0, 1, 2, 2, 3, 3, 3],
// d [0, 1, 2, 2, 3, 4, 4]
// ]    acad
function LCS(str1, str2) {
  let m = str1.length
  let n = str2.length
  let dp = [new Array(n + 1).fill(0)]
  for (let i = 1; i <= m; i++) {
    dp[i] = [0]
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) { // 如果该项相同，则取斜上方的数加一
        dp[i][j] = dp[i - 1][j - 1] + 1
      } else { //如果不相同，则取右边或上方较大的数
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
      }
    }
  }

  console.log(printfLCS(dp,str1,str2,m,n))

  return dp[m][n]
}

function printfLCS(dp, str1, str2, i, j) {
  if (i === 0 || j === 0) {
    return ''
  }
  if (str1[i - 1] == str2[j - 1]) {
    return printfLCS(dp, str1, str2, i - 1, j - 1) + str1[i - 1]
  } else {
    if (dp[i][j - 1] > dp[i - 1][j]) {
      return printfLCS(dp, str1, str2, i, j - 1)
    } else {
      return printfLCS(dp, str1, str2, i - 1, j)
    }
  }
}

let string1 = 'acbaed'
let string2 = 'abcadf'
console.log(LCS(string1, string2))